◀ Prev · Parts · Full · Next ▶

Given a feasible solution s ∈ ∈ S ( i ) {\displaystyle s\in S(i)} , with s ≠ ≠ s ∗ ∗ {\displaystyle s\neq s^{*}} , we would want a guarantee of the quality of the solution, which is a performance to be guaranteed (approximation factor).

Specifically, having A Π Π ( i ) ∈ ∈ S i {\displaystyle A_{\Pi }(i)\in S_{i}} , the algorithm has an approximation factor (or approximation ratio) of ρ ρ ( n ) {\displaystyle \rho (n)} if ∀ ∀ i ∈ ∈ I s . t . | i | = n {\displaystyle \forall i\in I\ s.t.|i|=n} , we have:

• for a minimization problem: c ( A Π Π ( i ) ) c ( s ∗ ∗ ( i ) ) ≤ ≤ ρ ρ ( n ) {\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)} , which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of ρ ρ ( n ) {\displaystyle \rho (n)} ;

• for a maximization problem: c ( s ∗ ∗ ( i ) ) c ( A Π Π ( i ) ) ≤ ≤ ρ ρ ( n ) {\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)} , which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of ρ ρ ( n ) {\displaystyle \rho (n)} ;

The approximation can be proven tight (tight approximation) by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.

◀ Prev · Parts · Full · Next ▶